//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 10⁵ 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 2046 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * [P76]_最小覆盖子串
 * @author cjl
 * @date 2022-08-05 18:29:07
 */
public class P76_MinimumWindowSubstring{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P76_MinimumWindowSubstring().new Solution();
          System.out.println("args = " + solution.minWindow("ADOBECODEBANC","ABC"));
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          /**
           * 双指针遍历：左右指针内不包含所需元素，则右指针右移；
           *        如果左右指针内包含所有所需元素，则左指针右移，找最小值；
           *       判断左右指针内元素是否包含t中所有元素，可通过两个map存储对比；
           * @param s
           * @param t
           * @return
           */
    public String minWindow(String s, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        Map<Character, Integer> currMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            Character key = t.charAt(i);
            tMap.put(key, tMap.getOrDefault(key,0) +1);
        }
        int left = 0; int right = 0;
        int resL = -1; int resR = -1;
        boolean start = false;
        while(right < s.length()){
            //过滤头部不相关字符
            if(!start && !tMap.containsKey(s.charAt(left))){
                left++;
                right++;
                continue;
            }else{
                start = true;
            }
            if(tMap.containsKey(s.charAt(right))){
                currMap.put(s.charAt(right), currMap.getOrDefault(s.charAt(right), 0) +1);
            }
            while(check(tMap,currMap) && left <= right){
                if(resR < 0 || resR - resL > right - left){
                    resL = left;
                    resR = right;
                }
                if(tMap.containsKey(s.charAt(left))){
                    currMap.put(s.charAt(left), currMap.getOrDefault(s.charAt(left),0) -1);
                }
                left++;
            }
            right++;
        }
        if(resL >= 0 && resR >= 0 ){
            return s.substring(resL, resR+1);
        }
        return "";
    }

    public boolean check(Map<Character, Integer> tMap,Map<Character, Integer> currMap){
        if(tMap.size() != currMap.size()){
            return false;
        }
        for(Character key : tMap.keySet()){
            if(tMap.get(key) > currMap.getOrDefault(key, 0)){
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }